#include <bits/stdc++.h>

using namespace std;

struct LCT
{
	struct node
	{
		int	val;
		node *	s[2],*fa;
		node() {}
		node(const int x) { val=x,s[0]=s[1]=fa=0; }

		node *	access()
		{
			for(node *p=this,q=0;p;q=p,p=p->fa)
				p->splay()->link(1,q)->update();
			return splay();
		}

		node *	splay()
		{
			while(!isroot() && !fa->isroot())
			(getlr()==fa->getlr()?fa->rot():rot()),rot();
			if(!isroot())rot();update(); return this;
		}
		
		node *	rot()
		{
			node *gfa=fa->fa;bool fl=fa->isroot();
			getlr()?link(0,fa->link(1,s[0])):link(1,fa->link(0,s[1]));
			fa->update();
			if(!fl)gfa->link(gfa->s[0]==fa,this);
			else	fa=gfa;  return this;
		}

	}U[110000];

	

int main()
{
	int	

	scanf("%d%d%d%d",&n,&m,&k,&type);

	for(i=1;i<=n;++i)
	{
		sacnf("%d%d",&x,&y);
		D[i]=S.link(x,y);
	}
	
	while(m--)
	{
		scanf("%d%d",&l,&r);
		if(type)l^=last_Ans,r^=last_Ans;
		printf("%d\n",last_Ans=n-Query(1,n,1,l,r,l));
	}

	return 0;
}
